#include <bits/stdc++.h>
#include<climits> 
#include <ctime>
#include "Union_find.hpp"
using namespace std;
 

//邻接矩阵
//一般适合用于存稠密图
//能快速判断两个点的权值关系

//邻接表
//一般用于村稀疏图，和Hash散列类似
//把与自身有关系的节点，以链表或者其他方式在自己节点下
//且对于有向的查找也具备优势
//但是确定两个顶点之前的权值以及连通性都较慢



//要求传入的 W重载了<,>关系运算符，在这份偏序关系中，MAX_W是其中最大值
template <class V, class W,W MAX_W = INT_MAX >
class  Graph
{   
    struct Edge
    {
        Edge(size_t Src,size_t Dst,W w)
        :_SrcI(Src)
        ,_DstI(Dst)
        ,_w(w)
        {

        }
        size_t _SrcI;
        size_t _DstI;
        W _w;
    };
    using Self = Graph<V, W, MAX_W>;
    std::vector<V> _vertex;          //存储顶点
    unordered_map<V, int> _IndexMap; // 顶点所对应的下标
    vector<vector<W>> _matrix;   //邻接矩阵s
    bool _IsDirection = false;
    
    

public:
    //图的创建
    //1. IO输入
    //2.读取文件
    //3.手动添加边
    void Matrix_Init(size_t n){
        _matrix.resize(n);
        for (size_t i = 0; i < _matrix.size();i++)
        {
            _matrix[i].resize(n,MAX_W);
        }
    }

    //默认是无向图加边
    Graph(const V* ver,size_t n,bool IsDirection = false)
    :_IsDirection(IsDirection)
    {
        _vertex.reserve(n);
        for (size_t i = 0; i < n;++i)
        {
            _vertex.push_back(ver[i]);
            _IndexMap[ver[i]] = i;
        }
        Matrix_Init(n);
    }
    
    Graph(const vector<V>& vertexes,size_t n,bool IsDirection = false)
    :_IsDirection(IsDirection)
    {
        _vertex(vertexes);
        for (size_t i = 0; i < n;++i)
        {
            _IndexMap[_vertex[i]] = i;
        }
        Matrix_Init(n);
    }
    Graph(vector<V>&& vertexes,size_t n,bool IsDirection = false)
    :_IsDirection(IsDirection)
    {
        _vertex(vertexes);
        for (size_t i = 0; i < n;++i)
        {
            _IndexMap[_vertex[i]] = i;
        }
        Matrix_Init(n);
    }
    size_t GetVertexIndex(const V&v)
    {
        //判断下是否存在这个点
        auto it = _IndexMap.find(v);
        if(it!=_IndexMap.end())
        {
            return it->second;
        }
        throw invalid_argument("invalid parameter:the Vertex is not existed.\n");
        //这里没有对不存在的点做增加处理
        return -1;
    }
    //提供添加有向边和无向边接口，该接口是覆盖性添加边。也就是对同一组边提供，后者权重会有效
    void AddEdge(const V& src,const V& dst,const W &w,bool IsDirection)
    {
        size_t SrcI = GetVertexIndex(src);
        size_t DstI = GetVertexIndex(dst);
 
        _matrix[SrcI][DstI] = w;
        if(!IsDirection)
        {
            _matrix[DstI][SrcI] = w;
        }
    }
    //提供默认接口，让用户选择默认添加什么边
    void AddEdge(const V& src,const V& dst,const W &w)
    {
        size_t SrcI = GetVertexIndex(src);
        size_t DstI = GetVertexIndex(dst);
 
        _matrix[SrcI][DstI] = w;
        if(!_IsDirection)
        {
            _matrix[DstI][SrcI] = w;
        }
    }
    //为了使得调用时构建单一的无向图或者有向图，提供两个常量以供使用
    bool UndirectedEdge = false;
    bool DirectedEdge = true;

    void SetAdd_EdgeIsdir(bool IsDirection)
    {
        _IsDirection = IsDirection;
    }
    
    bool IsDirectionGraph()
    {
        for (int i = 0; i < _matrix;i++)
        {
            for (int j = 0; j < i;j++)
            {
                if(_matrix[i][j]!=_matrix[j][i])
                {
                    return true;
                }
            }
        }
        return true;
    }
    void Print()
    {
        
        for (int i = 0; i < _vertex.size();i++)
        {
            cout <<"Vertex"<< "[" << i << "]"
                 << "->" << _vertex[i] << endl;

        }
        cout << endl;
        for (size_t i = 0; i < _matrix.size();i++)
        {
            for (size_t j = 0; j < _matrix.size();j++)
            {
                int tmp = _matrix[i][j];
                if(_matrix[i][j] ==MAX_W)
                {
                    tmp = -1;
                }
                printf("%10d   ", tmp);
            }
            cout << endl;
        }
    }

    void BFS(const V& Src)
    {
        list<int> q;
        q.push_back(GetVertexIndex(Src));
        vector<bool> label(_vertex.size(), 0);
        label[GetVertexIndex(Src)] = 1;
        

        //一圈一圈的向外扩展
        //可以定义两个Level，和LevelNum的变量统计每层的个数
        //类似二叉树打印层数一般
        int Level = 0, LevelNum = 1, NextLevelNum = 0;
        cout << "Level" << Level <<":" <<endl;
        while(!q.empty())
        {
            if(LevelNum>0)
            {
                
                for (int i = 0; i < _matrix.size();i++)
                {
                    if(_matrix[q.front()][i]!= MAX_W && !label[i])
                    {
                        cout << _vertex[q.front()] << "->"<<_vertex[i];
                        q.push_back(i);
                        label[i] = 1;
                        NextLevelNum++;
                        cout << endl;
                    }
                }
                LevelNum--;
                q.pop_front();
            }
            else{
                cout << endl;
                Level++;
                LevelNum = NextLevelNum;
                NextLevelNum = 0;
                cout << "Level" << Level <<":" <<endl;
            }
        }
    }


    void DFS(const V& Src)
    {
        vector<int> v(1, GetVertexIndex(Src));

        vector<bool> visited(_matrix.size(), 0);
        visited[GetVertexIndex(Src)] = 1;

        int sub = 0;
        while(sub>=0)
        {
            bool IsUp = 1;
            int now = sub;
            for (int i = 0; i < _matrix.size();i++)
            {
                if(_matrix[v[now]][i] != MAX_W && !visited[i])
                {
                    v.push_back(i);
                    sub++;
                    visited[i] = 1;
                    IsUp = 0;
                }
            }
            if(IsUp)
            {
                sub--;
            }
        }
        for(auto &i:v)
        {
            cout << _vertex[i] << "->";
        }
        cout << endl;
    }

    template <class Obj> 
    struct Cmp
    {
        operator()(const Obj& obj1,const Obj& obj2)
        {
            //大于来构成小顶堆
            return obj1._w >obj2._w ;
        }
    };
    

    //一个本身要连通的图，使用该算法才能有结果
    W Kruskal(Self& minTree)//返回最小生成树的权值
    {
        W t = 0;
        priority_queue<Edge,vector<Edge>,Cmp<Edge>> pq;
        UnionFindSet ufs(_matrix.size());
        int cnt = 0;
        for (int i = 0; i < _matrix.size(); i++)
        {
            for (int j = 0; j < _matrix.size();j++)
            {
                if(_matrix[i][j] != MAX_W)
                {
                    pq.push(Edge(i, j, _matrix[i][j]));
                }
            }
        }

        while(!pq.empty() && cnt <_matrix.size() - 1)
        {
            if(!ufs.IsSameSet(pq.top()._SrcI,pq.top()._DstI))
            {
                ufs.Union(pq.top()._SrcI, pq.top()._DstI);
                minTree.AddEdge(_vertex[pq.top()._SrcI],_vertex[pq.top()._DstI],pq.top()._w);
                t += pq.top()._w;
                cnt++;
            }
            pq.pop();
        }
        if(cnt < _matrix.size() - 1)
            return MAX_W;
        return t;
    }


    W Prim_ver1(Self& minTree,const V & Src)
    {
        W t = 0;
        size_t  SrcI= GetVertexIndex(Src);
        //初始化点集
        unordered_set<int> init_v;
        for (int i = 0; i < _matrix.size();i++)
        {
            init_v.insert(i);
        }
        vector<int> visited_v;
        
        visited_v.push_back(SrcI);
        init_v.erase(SrcI);

        W tmp = MAX_W;
        int j_sub = -1;
        bool Isfind = 1;
        while(!init_v.empty() &&  Isfind)
        {
            tmp = MAX_W;
            Isfind = 0;
            int i_sub = -1;
            for (int i = 0; i < visited_v.size();i++)
            {
                for (const auto &j: init_v)
                {
                    if(tmp>_matrix[visited_v[i]][j])
                    {
                        tmp = _matrix[visited_v[i]][j];
                        j_sub = j;
                        i_sub = visited_v[i];
                        Isfind = 1;
                    }
                }
            }
            if(Isfind)
            {
                init_v.erase(j_sub);
                visited_v.push_back(j_sub);
                minTree.AddEdge(_vertex[i_sub], _vertex[j_sub], _matrix[i_sub][j_sub]);
                t += tmp;
                
            }
        }
        if(!init_v.empty())
        {
            cout << "并非连通图\n";
            return MAX_W;
        }
        return t;
    }

    //上面是再找中间边的时候，时会出现n^2的情况
    //时间复杂度过大，因此修订
    W Prim_ver2(Self& minTree,const V & Src)
    {
        W t = 0;
        size_t  SrcI= GetVertexIndex(Src);
        unordered_set<int> visited_v;
        priority_queue<Edge, vector<Edge>, Cmp<Edge>> eq;

        for (int i = 0; i < _matrix.size();i++)
        {
            if(_matrix[SrcI][i] != MAX_W)
            {
                eq.push(Edge(SrcI,i,_matrix[SrcI][i]));
            }
        }
        
        visited_v.insert(SrcI);

        while(!eq.empty()){
            Edge min = eq.top();
            
            eq.pop();
            //判环，用hash效率就很高，同时分出是否在已知集合
            if(visited_v.find(min._DstI) != visited_v.end())
            {
                continue;
            }
            minTree.AddEdge(_vertex[min._SrcI], _vertex[min._DstI], min._w);
            visited_v.insert(min._DstI);
            t += min._w;
            // visited_v.insert(min._SrcI);
            for (int i = 0; i < _matrix.size();i++)
            {
                //保证边有效的同时，只添加还在外面的边
                if(_matrix[min._DstI][i] != MAX_W && visited_v.find(i) == visited_v.end())
                {
                    eq.push(Edge(min._DstI,i,_matrix[min._DstI][i]));
                }
            }
        }
        return t;
    }

    //返回改源路径最短值,
    int Dijkstra(const V& src,vector<W>& Distance,vector<int>* Parent_V_path)
    {
        int SrcI= GetVertexIndex(src);
        Parent_V_path->resize(_vertex.size());

        (*Parent_V_path)[SrcI] = SrcI;

        //存放目前起点到各个点的距离
        Distance.resize(_vertex.size(),MAX_W);
        Distance[SrcI] = 0;//自己就是0；

        //访问过的点
        vector<bool> visited(_vertex.size(),0);
        visited[SrcI]  = 1; 

        priority_queue<pair<W,int>,vector<pair<W,int>>,std::greater<pair<W,int>> >  V_queue;

        V_queue.push(pair(0,SrcI));


        while(!V_queue.empty())
        {
            pair<int,int> next(MAX_W,-1);
            int now = V_queue.top().second;
            V_queue.pop();

            for(int i = 0 ;i<_vertex.size();i++)
            {
                if(!visited[i] && _matrix[now][i] != MAX_W &&Distance[i] > _matrix[now][i] + Distance[now])
                {
                    Distance[i] = _matrix[now][i] + Distance[now];
                    (*Parent_V_path)[i] = now;

                    V_queue.push(pair(Distance[i],i));
                    
                }
            }
        }
        return 0;
    }

    //Disjkaral的路径打印
    void DisjkaralPrintPath(const V & v,const vector<W>& Distance,const vector<int>& parentpath)
    {
        int SrcI = GetVertexIndex(v);
        for(int i = 0;i<_vertex.size();i++)
        {
            cout<<v<<"->"<<_vertex[i]<<":"<<Distance[i];
            cout<<"       :";
            string s;
            // s += _vertex[i]+ "--";
            int t = i;
            while(t!= SrcI)
            {
                s.push_back(_vertex[t]);
                s+= "--";
                t = parentpath[t];
            }
            s+= v;
            std::reverse(s.begin(),s.end());
            cout<<s<<endl;
        }
    }

};





int Test_Graph()
{
    string a[] = {"Lisa", "Annie", "Jane", "Sara","Lucy","Charlotte"};
    Graph<string, int> g(a,sizeof(a)/sizeof(a[0]));
    g.AddEdge("Lisa", "Annie", 520);
    g.AddEdge("Jane", "Sara", 1314);
    g.AddEdge("Lisa", "Jane", 100);
    g.AddEdge("Lucy", "Charlotte", 770);
    g.AddEdge("Lucy", "Sara", 8013);
    g.AddEdge("Annie", "Lucy", 8888);
    g.AddEdge("Lisa", "Lucy", 9999);
    // g.BFS("Lisa");
    // g.DFS("Lisa");

    Graph<string, int> kg(a,sizeof(a)/sizeof(a[0]));
    int t =  g.Kruskal(kg);
    if(t!= INT_MAX)
    {
        kg.DFS("Lisa");
        cout << t << endl;
    }
    // cout << "不是连通图\n";

    Graph<string, int> pg(a,sizeof(a)/sizeof(a[0]));

    t = g.Prim_ver2(pg, "Sara");
    if(t != INT_MAX)
    {
        pg.DFS("Lisa");
        cout << t << endl;
        return 0;
    }
    cout << "不是连通图\n";
    return 0;
}

int Test_Graph2()
{
     char a[] = "abcdefghi";
    Graph<char, int> g(a, strlen(a));
    g.AddEdge('a', 'b', 4);
    g.AddEdge('a', 'h', 8);
    //g.AddEdge('a', 'h', 9);
    g.AddEdge('b', 'c', 8);
    g.AddEdge('b', 'h', 11);
    g.AddEdge('c', 'i', 2);
    g.AddEdge('c', 'f', 4);
    g.AddEdge('c', 'd', 7);
    g. AddEdge('d', 'f', 14);
    g. AddEdge('d', 'e', 9);
    g.AddEdge('e', 'f', 10);
    g.AddEdge('f', 'g', 2);
    g.AddEdge('g', 'h', 1);
    g.AddEdge('g', 'i', 6);
    g.AddEdge('h', 'i', 7);
    Graph<char, int> kg(a,sizeof(a)/sizeof(a[0]));
    int t =  g.Kruskal(kg);
    if(t!= INT_MAX)
    {
        kg.DFS('a');
        cout << t << endl;
    }
    // cout << "不是连通图\n";

    Graph<char, int> pg(a,sizeof(a)/sizeof(a[0]));

    t = g.Prim_ver2(pg, 'a');
    if(t != INT_MAX)
    {
        pg.DFS('a');
        cout << t << endl;
        return 0;
    }
    cout << "不是连通图\n";
    return 0;
}


int Test_graph3()
{
    const char* str = "syztx";
    Graph<char, int> g(str, strlen(str),true);
    g.AddEdge('s', 't', 10);
    g.AddEdge('s', 'y', 5);
    g.AddEdge('y', 't', 3);
    g. AddEdge('y', 'x', 9);
    g. AddEdge('y', 'z', 2);
    g. AddEdge('z', 's', 7);
    g. AddEdge('z', 'x', 6);
    g.AddEdge('t', 'y', 2);
    g.AddEdge('t', 'x', 1);
    g. AddEdge('x', 'z', 4);

    vector<int> dist;
    vector<int> parentPath;
    g.Dijkstra('s', dist, &parentPath);
    g.DisjkaralPrintPath('s',dist,parentPath);
    return 0;
}